The present invention is related to modular robots, and in particular, software for modular robots.
Modular hardware that can reconfigure itself is usually referred to as a self-reconfigurable modular robot. A self-reconfigurable modular robot is composed of many identical modules and does not resemble the common view of a robot. Each module typically has a power source, processor, memory, motor, sensors, singly or in combination. The modules can attach to and detach from each other. Individual modules on their own can do little, but the robot, using the capabilities of the individual modules, can reconfigure itself to solve problems.
Advantages of self-reconfigurable modular robots include physical adaptability to varying problems and environments, robustness since identical modules can replace each other in the event of failure, and economies of scale in the manufacturing process.
Examples of self-reconfiguring modular robots include:
1) CMU""s I-cubes as described in C. xc3x9cnsal, H. Kilixc3xa7xc3xa7xc3x6te, P. K. Khosla, xe2x80x9cA 3-D Modular Self-Reconfigurable Bipartite Robotic System: Implementation and Motion Planning,xe2x80x9d submitted to Autonomous Robots Journal, special issue on Modular Reconfigurable Robots, 2000;
2) USC-ISI""s Spider Link Models, P. Will, A. Castano and W-M. Shen, xe2x80x9cRobot Modularity for Self-Reconfiguration,xe2x80x9d Proc. SPIE Sensor Fusion and Decentralized Control II, pp. 236-245, Boston, September 1999.
3) Dartmouth""s Molecular Robots, Kotay, K., Rus, D., Vona, M. and McGray, C., xe2x80x9cThe Self-reconfiguring robotic molecule: design and control algorithmsxe2x80x9d. In Proceeding of the 1998 International Conference on Intelligent Robots and Systems, 1998;
4) Crystalline Robots, Rus, D., M. Vona, xe2x80x9cSelf-Reconfiguration Planning with Compressible Unit Modulesxe2x80x9d. In 1999 IEEE Int. Conference on Robotics and Automation;
5) MSU""s Reconfigurable Adaptable Micro-Robot, R. L. Tummala, R. Mukherjee, D. Aslam, N. Xi, S. Mahadevan, J. Weng, xe2x80x9cReconfigurable Adaptable Micro-Robotxe2x80x9d, Proc. 1999 IEEE International Conference on Systems, Man, and Cybernetics, Tokyo, Japan, October 1999;
6) Johns Hopkins University, s Metamorphic Robots, Amit Pamecha, Imme Ebert-Uphoff, Gregory S. Chirikjian, AUseful Metrics for Modular Robot Motion Planning, IEEE Transactions on Robots and Automation, pp. 531-545, Vol.13, No.4, August 1997 (xe2x80x9cPamechaxe2x80x9d);
7) Xerox PARC""s PolyBot, Yim, Mark, Duff, David G., Roufas, Kimon D. IEEE Intl. Conf. On Robotics and Automation (ICRA), 2000; and,
8) Proteo robots Hristo Bojinov, Arancha Casal, Tad Hogg, xe2x80x9cEmergent Structures in Modular Self-reconfigurable Robotsxe2x80x9d, IEEE Intl. Conf. on Robotics and Automation (ICRA) 2000.
It is difficult to design effective software for self-reconfiguring modular robots. It is desirable to have the software completely decentralized and completely autonomous, so that tasks can be performed without reference to a central controller, whether human or machine. The hope is that eventually hundreds, or even millions, of modules will work together. Decentralized control takes advantage of the computational power of the individual modules and requires less communication bandwidth. All modules typically run the same software program, but behave differently depending on individual sensor values, internal state, and messages received from nearby modules.
Thus, there is a desire to provide decentralized software controllers for self-reconfigurable modular robots that act at a local level but achieve useful global behavior.
A method and computer-readable medium is provided for designing a software program for a module in a self-reconfigurable robot.
The method includes the step of providing a plurality of software functions for performing a respective plurality of module functions. A first plurality of software programs for solving a task is constructed from the plurality of software functions. The first plurality of software programs are executed to obtain a plurality of results. The method includes the step of providing a fitness function for obtaining a fitness function value for the first plurality of software programs. A second plurality of software programs is selected from the first plurality of software programs based on the respective fitness function values. The second plurality of software programs is modified, by a genetic operation, to form a third plurality of software programs.
According to an aspect of the present invention, the genetic operation is a crossover, mutation and/or cloning operation, singly or in combination.
According to an aspect of the present invention, the crossover operation includes obtaining respective parse tree representations of a first and second xe2x80x9cparentxe2x80x9d computer program in the second plurality of software programs to create a first and second xe2x80x9cchildxe2x80x9d software program by exchanging a randomly selected subtree between the first and second xe2x80x9cparentxe2x80x9d computer program.
According to another aspect of the present invention, the mutation operation includes obtaining a parse tree representation of a first software program in the second plurality of computer programs The parse tree includes a first subtree. The first subtree is randomly selected and replaced with a randomly created second subtree.
According to another aspect of the present invention, the cloning operation includes copying a first software program in the second plurality of software programs.
According to another aspect of the present invention, the plurality of functions include: (GetMemory index), (MoveLine direction), (MoveSingle direction), (ReadMessage direction), (ReadSensorSelf direction), (ReadSensorSelfBroken direction), (ReadSensorWall direction), (Rotate direction), (SendMessage message direction) (SetMemory Index value), (BlockMove xpos xneg ypos yneg), (And), (If), (Less), (Divide), (Modules) functions, either singly or in combination.
According to another aspect of the present invention, the module is a sliding module, a rotating module and/or a compressible module.
According to another aspect of the present invention, the task is moving a self-reconfigurable robot through a narrow passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot through a switchback passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot having a broken module through a switchback passage.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot through a switchback passage and ejecting a broken module.
According to another aspect of the present invention, the task is forming a bridge over a gap.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot toward a goal.
According to another aspect of the present invention, the task is moving the self-reconfigurable robot toward a goal in the presence of obstacles.
According to another aspect of the present invention, a module includes a sensor, a motor and a power source, singly or in combination.
According to another aspect of the present invention, the fitness function includes measuring the distance between a robot location and a selected location.
According to another aspect of the present invention, a module in a self-reconfigurable robot with software created by genetic programming is provided. The module includes a processor coupled to memory. The memory stores a software program for solving a problem, wherein the software program is constructed from a genetic program.
An article of manufacture, including computer readable memory is provided. The computer readable memory includes a first plurality of software functions for performing a respective plurality of module tasks in a self-reconfigurable robot. A first software program randomly selects a first plurality of functions to form a plurality of software programs. A fitness function obtains a respective plurality of fitness function values for the respective first plurality of software programs. A second software program selects a second plurality of programs from the first plurality of programs based on the respective plurality of fitness function values. A third software program constructs a third plurality of software programs from the second plurality of software programs by a genetic operation.